package org.company.earth.arithmetic;

import java.util.List;

public class InsertSort<T> extends BaseSort<T> {

    @Override
    public void sort(List<T> list) {
        for(int i = 1; i < list.size() ; i++) {
            this.insertSort(list, i);
        }
    }
    
    /**
     * 认为从[0,p-1]的数据已经排序完成
     * 时间复杂度 O(N^2)
     * 
     * @param list
     * @param p
     */
    protected void insertSort(List<T> list,int p) {
        this.insertSort(list, p, 1);
    }
    
    /**
     * 排序区间[0,p]
     * @param list
     * @param p,排序区间[0,p]
     * @param step,排序步长
     */
    protected void insertSort(List<T> list,int p,int step) {
        while((p-=step) >= 0 && gt(list.get(p),list.get(p+step))) {
            this.swap(list, p, p+step);
        }
        this.print(list);
    }
}
